125. Valid Palindrome

解題程式碼

var isPalindrome = function (s) {
  const loweCaseStr = s.toLowerCase().replace(/[^a-zA-Z0-9]/g, '');
  return loweCaseStr === loweCaseStr.split('').reverse().join('');
};

解題思路、演算法

先用正規表達式整理字串，然後將整理過後的字串反轉過後和整理過後的字串做比對

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料

這題用 two pointers 做出來的效能更好，請參考此解答

242. Valid Anagram

解題程式碼

var isAnagram = function(s, t) {
  return s.split('').sort().join('') === t.split('').sort().join('')
};

解題思路、演算法

這題我的解法很簡潔，將所有字母做個排序去比對，但是執行速度和記憶體用量只有贏三成的人

所以底下補充 時間複雜度: (O(n)) 的解法:

使用 hash table 去儲存字串每個字母出現的次數，然後和另一字串字母出現的次數一一做比對

解法的時間、空間複雜度

時間複雜度: O(n * logn)
空間複雜度: O(n)

參考資料

🔥Easy Solutions in Java 📝, Python 🐍, JavaScript 🖥️and C++ 🧐Look at once 💻

3. Longest Substring Without Repeating Characters

解題程式碼

var lengthOfLongestSubstring = function (s) {
  let longL = 0;
  let startIndex = 0;
  let charMap = new Map();

  for (let i = 0; i < s.length; i++) {
    if (charMap.has(s[i])) {
      startIndex = Math.max(startIndex, charMap.get(s[i]) + 1);
    }
    longL = Math.max(longL, i - startIndex + 1);
    charMap.set(s[i], i);
  }

  return longL;
};

// "abcabcbb" i = 3，startIndex = 1，longL = 3
// "abcabcbb" i = 4，startIndex = 2，longL = 3
// "abcabcbb" i = 5，startIndex = 3，longL = 3
// "abcabcbb" i = 6，startIndex = 5，longL = 3
// "abcabcbb" i = 7，startIndex = 7，longL = 3

解題思路、演算法

使用 Sliding Window 解題，使用一個 pointer 變數儲存當前子陣列的起點，並用一個 hashTable 儲存字串內各字元的索引最大值，如果當前遍歷的字元有出現在 hashTable，就代表字母重複了，因此去更新 pointer 的值。

注意更新最大長度時記得 +1，因為索引是從 0 開頭

解法的時間、空間複雜度

時間複雜度: O(n)
空間複雜度: O(n)

參考資料